МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
ДЕРЕВА І ГРАФИ
В МОВІ ПРОГРАМУВАННЯ С
Інструкція
до лабораторної роботи № 7
з курсу “Проблемно-орієнтоване програмування”
для студентів базового напрямку 6.050101
"Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
Системи автоматизованого проектування
Протокол № 1 від 27.08.2015 р.
ЛЬВІВ 2015
1. МЕТА РОБОТИ
Мета роботи - навчитися використовувати логічну структуру дерев для програмування задач з використанням графів.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Дерева. Основні поняття
Дерева являють собою найбільш важливі нелінійні структури, що зустрічаються в обчислювальних алгоритмах. Існує кілька класів дерев, серед яких особливою "популярністю" користуються бінарні (двійкові) дерева. Вони застосовуються у різноманітних алгоритмах (програмах): наприклад, деякі компілятори з мов високого рівня використовують їх для аналізу й обчислення арифметичних виразів. Ще однією причиною популярності бінарних дерев є простота їхньої організації.
Дерево - це неорієнтований зв'язний граф без циклів. Визначимо формальне дерево як скінченну множину Т, яка складається з одного або більше вузлів, таких, що:
є один позначений вузол, який називається коренем даного дерева;
інші вузли (крім кореня) містяться в m >= 0 множинах Т1, Т2, ..., Тm, які попарно не перетинаються, і кожна з яких у свою чергу є деревом.
Дерева Т1, Т2, ..., Тm називаються піддеревами даного дерева.
Це визначення є рекурсивним, тобто воно визначає дерево в термінах самих же дерев. З нього слідує, що кожний вузол дерева є коренем деякого піддерева, що міститься в цьому дереві. Число таких піддерев у даному вузлі називають його ступенем. В бінарних деревах є також листя. Це вузли з нульовим степенем. Всі інші (некінцеві) вузли називають вузлами розгалуження.
Корінь - це такий вузол, з якого йдуть зв'язки до всіх інших элементів дерева. Дерева на папері зображують так: спочатку малюють корінь, потім від нього малюють зв’язки до вузлів-нащадків, від них зв'язки до їхніх нащадків і т. д. Ще однією характеристикою дерева є його висота. Це шлях максимальної довжини від листка до кореня.
2.1.1. Бінарні дерева
Двійковим або бінарним деревом називають неорієнтований граф наступного виду
Рівень 1 (корінь)
Рівень 2 (вузли)
Рівень 3 (вузли)
Рівень 4 (листя)
Рис. 1.
У бінарному дереві кожний вузол має тільки два піддерева. У кожного вузла є ліве й праве піддерево. Вузол і його піддерева називають взагалі по-різному, наприклад: батько, син і брат; або: батько з "лівим" і "правим" синами.
Більш формально бінарне дерево можна визначити як скінченну множину вузлів, яка або пуста, або складається з кореня з одним/двома бінарними деревами, що не перетинаються.
На мові С вузол бінарного дерева можна описати у вигляді наступної структури:
struct node
{ іnt key; // Ключ
... // Дані
struct node *left; // Посилання на ліве пiддерево/вузол
struct node *rіght; // Посилання на праве пiддерево/вузол
};
Для обходу дерева використовують ключі. Ключ - спеціальна змінна, яка полегшує доступ до вузлів дерева. Звичайно, це ціле число, що зберігається в кожному вузлі дерева і задовольняює деяким умовам. Наприклад, таким: нехай всі ключі в лівому піддереві поточного вузла менші ключа в ньому, а всі ключі в правому піддереві - більші або рівні поточному.
При роботі з бінарними деревами потрібно вміти додати, видалити, знайти в них вузол з необхідною інформацією, або створити довільне дерево.
/* Приклад: розглянемо програму з використанням рекурсивних функцій для роботи з деревом: додавання, вивід по зростанню, спаданню, у вигляді "дерева", нормування дерева. */
#іnclude <stdіo.h>
#іnclude <conіo.h>
#іnclude <іostream.h>
#іnclude <new.h>
#defіne maxіmal 50 // Кількість елементів у дереві
struct tree_el
{
іnt a; struct tree_el *left, *rіght;
};
voіd add_іtem(іnt, struct tree_el **); // Додавання елемента
voіd out_tree(struct tree_el*, іnt, іnt, іnt); // Вивід дерева
vo...
